package edu.vt.ece.rt.benchmark.rbtree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

import edu.vt.ece.rt.benchmark.BenchmarkThread;
import edu.vt.ece.rt.dstm.Context;
import edu.vt.ece.rt.dstm.ContextDelegator;
import edu.vt.ece.rt.dstm.QObject;
import edu.vt.ece.rt.dstm.TMProxy;
import edu.vt.ece.rt.quorum.ClustersManager;
import edu.vt.ece.rt.quorum.Resource;
import edu.vt.ece.rt.quorum.util.AbortException;
import edu.vt.ece.rt.quorum.util.Names;
import edu.vt.ece.rt.util.Logger.Logger;

public class RBTree extends QObject {

	float val;
	String left;
	String right;
	String id;
	String color;
	static boolean first = true;
	static ArrayList<String> leaves = new ArrayList<String>();

	public static String black = "black";
	public static String red = "red";

	public RBTree(String id, int v, String left, String right, String color) {
		this.val = v;
		this.left = left;
		this.right = right;
		this.id = id;
		this.color = color;
		Resource.putQObject(getId(), this);
	}

	
	public static RBTree nullLeaf = new RBTree("null-leaf", 0, null, null, black);
	public static String nullLeafId = "null-leaf";

	
	public RBTree() {

	}


	public float getVal() {
		return val;
	}

	public void setVal(float v) {
		val = v;
	}

	public String getLeft() {
		return left;
	}

	public void setLeft(String l) {
		left = l;
	}

	public String getRight() {
		return right;
	}

	public void setRight(String r) {
		right = r;
	}

	@Override
	public String getId() {
		return id;
	}

	public void setId(String id) {
		this.id = id;
	}

	public String getColor() {
		return color;
	}

	public void setColor(String color) {
		this.color = color;
	}

	@Override
	public QObject clone() {
		RBTree b= new RBTree();
		b.setId(getId());
		b.setVersion(getVersion());
		b.setCloneOwner(getCloneOwner());
		b.setLeft(getLeft());
		b.setRight(getRight());
		b.setVal(getVal());
		b.setColor(getColor());
		return b;
	}

	static public void addInit(int val) {

		String root = "root";
		String currNodeId = root;
		RBTree bst = nullLeaf;
		boolean left  = true;

		System.out.println("Starting from root");
		do {
			bst = (RBTree) Resource.getQObject(currNodeId);
			System.out.println("curr node is "+currNodeId + " with color "+bst.getColor());
			if (val <= bst.getVal()) {
				currNodeId = bst.getLeft();
				left = true;
			} else {
				left = false;
				currNodeId = bst.getRight();
			}
		} while (! (currNodeId.equals(nullLeaf.getId())));

		String color;
		if (bst.getColor().equals(black)) {
			color = red;
//			color = black;
		} else {
			color = black;
		}

		RBTree newNode = new RBTree(Integer.toString(val), val, nullLeafId, nullLeafId, color);
		System.out.println("Adding node "+val + " with color "+color);

		if (left) {
			bst.setLeft(newNode.getId());
		} else {
			bst.setRight(newNode.getId());
		}
	}


	static void createBtree(int start, int end) throws Throwable {

		int mid = (start +  end)/2;
		int lStart = 0, rStart = 0, lEnd = 0, rEnd = 0;
		//		System.out.println("Start=" +start);System.out.println("End=" +end);

		if (end == (start + 1)) {
			addInit(start);
			addInit(end);
			//			System.out.println("Start1=" +start);System.out.println("End1=" +end);
			return;
		} else if (start == end) {
			//			System.out.println("start=end" +start);
			addInit(start);
		} else {
			//			System.out.println("Mid=" +mid);
			if (first) {
				new RBTree("root", mid, nullLeafId, nullLeafId, black);
				first = false;
			} else {
				addInit(mid);
			}
			lStart = start;
			lEnd = mid - 1;
			createBtree(lStart, lEnd);
			rStart = mid + 1;
			rEnd = end;
			createBtree(rStart, rEnd);
		}
	}

	public static Boolean testRotate(float val, Context parentContext) {

		Boolean found = false;
		Long priority = System.currentTimeMillis();

		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsRoot(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("find element "+val+" in rbtree");
			context.sanityNested();
			context.setPriority(priority);

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				String root = "root";
				HashMap<String, RBTree> map = new HashMap<String, RBTree>();
				
				RBTree A = (RBTree) TMProxy.getTMProxy().write(root, context.getContextId());
				RBTree B = (RBTree) TMProxy.getTMProxy().write(A.getRight(), context.getContextId());
				leftRotate(A, B, map, context);
				
				System.out.println("After rotation");
				System.out.println("Root val is "+A.getVal() +" with id "+ A.getId()+ " left id is "+A.getLeft()+ " right is "+A.getRight());
				System.out.println("New left val is "+B.getVal() +" with id "+ B.getId()+" left id is "+B.getLeft()+ " right is "+B.getRight());

				
				if (TMProxy.getTMProxy().requestCommit(context.getContextId())) {
					context.unsetParent(parentContext);
					return found;
				}

			} catch (AbortException e) {
				e.touch();
			}
		}
		Logger.fetal("Unable to complete transaction in given number of tries");

		return found;
	}

	public static Boolean find(float val, Context parentContext) {

		Boolean found = false;
		Long priority = System.currentTimeMillis();

		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsRoot(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("find element "+val+" in rbtree");
			context.sanityNested();
			context.setPriority(priority);

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				String root = "root";
				String currNodeId = root;
				RBTree bst = nullLeaf;
				do {
					bst = (RBTree) TMProxy.getTMProxy().read(currNodeId, context.getContextId());
					Logger.debug(context.getContextId()+ " currently at "+bst.getVal() + " with color "+bst.getColor());
					if (val <= bst.getVal()) {
						currNodeId = bst.getLeft();
					} else {
						currNodeId = bst.getRight();
					}
				} while (bst.getVal() != val && !(currNodeId.equals(nullLeafId)));

				if (bst.getVal() == val) {
					found = true;
				}

				if (TMProxy.getTMProxy().requestCommit(context.getContextId())) {
					context.unsetParent(parentContext);
					return found;
				}

			} catch (AbortException e) {
				e.touch();
			}
		}
		Logger.fetal("Unable to complete transaction in given number of tries");

		return found;
	}

    public static void write(int localObjectsCount, boolean nesting) {
		Context parentContext = null;
		Long priority = System.currentTimeMillis();
		Boolean delOp;
		
		ArrayList<Integer> arr = new ArrayList<Integer>();
		ArrayList<Boolean> booleanVal = new ArrayList<Boolean>();

		Random random = new Random();
		for (int j = 0; j < Integer.getInteger(Names.calls); j++ ) {
			arr.add(random.nextInt(localObjectsCount));

			if (random.nextInt(100) > 50) {
				booleanVal.add(true);
			} else {
				booleanVal.add(false);
			}

		}
		
		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsRoot(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setDescription("starting root transaction");
			context.sanityNested();
			context.setPriority(priority);


			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {

				for (int j = 0; j < arr.size();j++) {

					int val = arr.get(j);
					
					delOp = booleanVal.get(j);

					if (delOp) {
						Logger.debug("delete op with val " +val);
						if (nesting)
							delete(val, context);
						else
							deleteWork(val, context);
					} else {
						Logger.debug("delete op with val " +val);
						if (nesting)
							add(val, context);
						else
							addWork(val, context);
					}
				}

				if (TMProxy.getTMProxy().requestCommit(context.getContextId())) {
					context.unsetParent(parentContext);
					return;
				}

			}  catch (AbortException e) {
				e.touch();
			}
		}
	
    }
	
	
	public static String add(float val, Context parentContext) throws AbortException {

		String add = nullLeafId;
		Long priority = System.currentTimeMillis();


		for (int i = 0; i < 0x7fffffff; i++) {


			((BenchmarkThread)Thread.currentThread()).collectStatsInner(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setPriority(priority);
			context.setDescription("add element "+ val +" in bucket");
			context.sanityNested();

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {
				addWork(val , context);

				context.mergeParent();
				return add;
			} catch (AbortException e) {	
				if (e.getTransaction().longValue() != context.getContextId().longValue()) {
					Logger.debug("Exception in parent transaction "+e.getTransaction());
					throw e;
				} else {
					Logger.debug("Exception in current transaction "+e.getTransaction());
				}
			}
		}

		return add;
	}

	public static void addWork(float val, Context context) throws AbortException{
		String root = "root";
		String currNodeId = root;
		RBTree bst = nullLeaf;
		boolean left = true;
		HashMap<String, RBTree> map = new HashMap<String, RBTree>();

		do {
			bst = (RBTree) TMProxy.getTMProxy().read(currNodeId, context.getContextId());
			Logger.debug("curr node is "+bst.val);
			if (val <= bst.getVal()) {
				currNodeId = bst.getLeft();
				left = true;
			} else {
				left = false;
				currNodeId = bst.getRight();
			}

			if (!(currNodeId.equals(nullLeafId))) {
				map.put(currNodeId, bst);
				Logger.debug("Putting parent of "+currNodeId + " as "+bst.val);
			}	
		} while (!(currNodeId.equals(nullLeafId)));

		if (currNodeId.equals(nullLeafId)) {
			Context dummy = ContextDelegator.getNestedContext();
			String id = Long.toString(dummy.getContextId());
			RBTree b = new RBTree();
			b.setId(id);
			b.setVal(val);
			b.setLeft(nullLeafId);
			b.setRight(nullLeafId);
			b.setColor(red);
			context.addToCreateSet(b);
			bst = (RBTree) TMProxy.getTMProxy().write(bst.getId(), context.getContextId());
			map.put(id, bst);
			if (left) {
				bst.setLeft(b.getId());
				Logger.debug("Setting left node id as "+b.getId() + " for "+bst.val);
			} else {
				bst.setRight(b.getId());
				Logger.debug("Setting right node id as "+b.getId() + " for "+bst.val);
			}
			Logger.debug("Added new node with val "+val+" with parent as "+bst.val);
			rebalanceAdd(b, map, context);
		}
	}

	public static void rebalanceAdd(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		insertCase1(N, map, context);
	}

	public static  void insertCase1 (RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		Logger.debug("Case 1");
		if (N.getId().equals("root")) {
			Logger.debug("Reached root coloring black and returning");
			N = (RBTree) TMProxy.getTMProxy().write(N.getId(), context.getContextId());
			N.setColor(black);
		} else {
			insertCase2(N, map, context);
		}
	}

	public  static void insertCase2(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {

		RBTree parent = getParentWritableCopy(N, map, context); 
		Logger.debug("Case 2");

		if (parent.getColor().equals(black)) {
			Logger.debug("Parent "+ parent.val + " is black");
			return;
		} else {
			Logger.debug("Case 3");

			// g cannot be null, see in wiki for explanation
			RBTree g = getParentWritableCopy(parent, map, context);

			boolean left = false;

			if (!g.getLeft().equals(nullLeafId) && g.getLeft().equals(parent.getId())) {
				left = true;
			}

			RBTree u = nullLeaf;

			if (left) {
				if (!g.getRight().equals(nullLeafId))
					u = (RBTree) TMProxy.getTMProxy().write(g.getRight(), context.getContextId());
			} else {
				if (!g.getLeft().equals(nullLeafId))
					u = (RBTree) TMProxy.getTMProxy().write(g.getLeft(), context.getContextId());
			}

			if (!u.getId().equals(nullLeafId) 
					&& u.getColor().equals(red)) {
				parent.setColor(black);
				u.setColor(black);
				g.setColor(red);
				insertCase1(g, map, context);
			} else {	
				insertCase4(N, map, context);
			}
		}		
	}

	public  static  void insertCase4(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {

		Logger.debug("Case 4");
		RBTree parent = getParentWritableCopy(N, map, context);
		RBTree g = getParentWritableCopy(parent, map, context);

		if (!parent.getRight().equals(nullLeafId) && 
				!g.getLeft().equals(nullLeafId) &&
				parent.getRight().equals(N.getId()) 
				&& parent.getId().equals(g.getLeft())) {

			leftRotate(parent, N, map, context);
			N = (RBTree) TMProxy.getTMProxy().write(N.getLeft(), context.getContextId());

		} else if (!parent.getLeft().equals(nullLeafId) &&
				!g.getRight().equals(nullLeafId) &&
				parent.getLeft().equals(N.getId()) &&
				parent.getId().equals(g.getRight())) {
			rightRotate(parent, N, map, context);
			Logger.debug("Right rotation on "+ parent.val);
			N = (RBTree) TMProxy.getTMProxy().write(N.getRight(), context.getContextId());
		}

		insertCase5(N, map, context);


	}

	public  static  void insertCase5(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		Logger.debug("Case 5");

		RBTree p = getParentWritableCopy(N, map, context);
		RBTree g = getParentWritableCopy(p, map, context);

		p.setColor(black);
		g.setColor(red);

		if (N.getId().equals(p.getLeft())) {
			rightRotate(g, p, map, context);
		} else {
			leftRotate(g, p, map, context);
		}
	}

	public static void updateMap(String child, RBTree parent, HashMap<String, RBTree> map) {
		
		if (!child.equals(nullLeafId))
			map.put(child, parent);
	}

	public  static  void leftRotate (RBTree A, RBTree B, HashMap<String, RBTree> map, Context context) throws AbortException {
		Logger.debug("Left rotation on "+A.val);

		boolean left = false;

		if (A.getId().equals("root")) {
			System.out.println("might be because of you!!!!");
			Logger.debug("might be because of you!!!!");
			A = (RBTree) TMProxy.getTMProxy().write(A.getId(), context.getContextId());
			float val = A.getVal();
			String leftId = A.getLeft();
			String rightId = B.getLeft();
			A.setVal(B.getVal());
			A.setRight(B.getRight());
			updateMap(B.getRight(), A, map);
			A.setLeft(B.getId());
			updateMap(B.getId(), A, map);
			
			// set up B now
			B.setVal(val);
			B.setLeft(leftId);
			updateMap(leftId, B, map);
			B.setRight(rightId);
			updateMap(rightId, B, map);
			
		} else {

			RBTree parent =  getParentWritableCopy(A, map, context);

			if (parent.getLeft() != null && 
					parent.getLeft().equals(A.getId())) {
				left = true;
			} else {
				left = false;
			}

			A.setRight(B.getLeft());
			updateMap(B.getLeft(), A, map);

			B.setLeft(A.getId());
			updateMap(A.getId(), B, map);

			if (left)
				parent.setLeft(B.getId());
			else
				parent.setRight(B.getId());
			updateMap(B.getId(), parent, map);

		}
	}

	public   static void rightRotate (RBTree A, RBTree B, HashMap<String, RBTree> map, Context context) throws AbortException {
		Logger.debug("Right rotation on "+A.val);

		boolean left = false;

		if (A.getId().equals("root")) {

			System.out.println("might be because of you!!!!");
			Logger.debug("might be because of you!!!!");
			float val = B.getVal();
			String leftId =  B.getRight();
			String rightId =  A.getRight();
			
			
			A.setVal(B.getVal());
			A.setLeft(B.getLeft());
			updateMap(B.getLeft(), A, map);
			A.setRight(B.getId());
			updateMap(B.getId(),A, map);
			
			B.setVal(val);
			B.setLeft(leftId);
			updateMap(leftId,B, map);
			B.setRight(rightId);
			updateMap(rightId,B, map);
			
		} else {

			RBTree parent = getParentWritableCopy(A, map, context);

			if (parent.getLeft() != null && 
					parent.getLeft().equals(A.getId())) {
				left = true;
			} else {
				left = false;
			}

			A.setLeft(B.getRight());
			updateMap(B.getRight(), A, map);

			B.setRight(A.getId());
			updateMap(A.getId(), B, map);

			if (left)
				parent.setLeft(B.getId());
			else
				parent.setRight(B.getId());
			updateMap(B.getId(), parent, map);
		}
	}

	public  static RBTree getParentWritableCopy(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {

		RBTree curr = map.get(N.getId());
		Logger.debug(context.getContextId()+ " Looking for parent of "+N.getId());
		Logger.debug(context.getContextId()+ " Parent of curr is "+curr.getVal() +" id is "+curr.getId());
		return (RBTree) TMProxy.getTMProxy().write(curr.getId(), context.getContextId());
	}


	public static String delete(float val, Context parentContext) throws AbortException {

		String delete = null;
		Long priority = System.currentTimeMillis();


		for (int i = 0; i < 0x7fffffff; i++) {

			((BenchmarkThread)Thread.currentThread()).collectStatsInner(i);
			Context context = ContextDelegator.getNestedContext();
			context.setParent(parentContext);
			context.setPriority(priority);
			context.setDescription("delete element "+ val +" in bucket");
			context.sanityNested();

			Logger.debug("----Started----- R Transaction "+context.getContextId()+" on "+ClustersManager.baseClusterId);
			try {
				deleteWork(val , context);
				context.mergeParent();
				return null;
				
			} catch (AbortException e) {	
				if (e.getTransaction().longValue() != context.getContextId().longValue()) {
					Logger.debug("Exception in parent transaction "+e.getTransaction());
					throw e;
				} else {
					Logger.debug("Exception in current transaction "+e.getTransaction());
				}
			}
		}

		return delete;
	}

	public static void deleteWork(float val, Context context) throws AbortException{
		String root = "root";
		String currNodeId = root;
		RBTree bst = null;
		HashMap<String, RBTree> map = new HashMap<String, RBTree>();
		boolean left = true;

		do {
			bst = (RBTree) TMProxy.getTMProxy().read(currNodeId, context.getContextId());
			Logger.debug(context.getContextId()+ " curr node is "+bst.val +" id is "+bst.getId());
			
			if (bst.getVal() == val)
				break;

			if (val < bst.getVal()) {
				currNodeId = bst.getLeft();
				left = true;
			} else {
				currNodeId = bst.getRight();
				left = false;
			}

			if (!(currNodeId.equals(nullLeafId))) {
				map.put(currNodeId, bst);
				Logger.debug(context.getContextId()+ " Putting parent of "+currNodeId + " as "+bst.val);
			}
		} while (!(currNodeId.equals(nullLeafId)));


		if (bst.getVal() == val) {
			String leftTreeId = bst.getLeft();
			String rightTreeId = bst.getRight();
			RBTree currTree = nullLeaf;
			String NId = nullLeafId;
			currTree = bst;
			boolean leftSide = false;
			
			if (leftTreeId.equals(nullLeafId) && rightTreeId.equals(nullLeafId)) {
				// not check for null parent as script will not let such situation to rise
				// where root is the only node left
				
				Logger.debug(context.getContextId()+ " Deleting leaf and currTree is "+currTree);
				
			} else if (!(leftTreeId.equals(nullLeafId))) {
				String curr = leftTreeId;
				left = true;
				leftSide = true;
				do {
					RBTree parent = currTree;
					currTree = (RBTree) TMProxy.getTMProxy().read(curr, context.getContextId());
					map.put(curr, parent);
					Logger.debug(context.getContextId()+ " moving to right "+currTree.getVal());
					curr = currTree.getRight();
					if (!(curr.equals(nullLeafId)))
						left = false;
				} while (!(curr.equals(nullLeafId)));
				Logger.debug(context.getContextId()+ " Deleting from left leaf and currTree is "+currTree.getVal());
			} else if (!(rightTreeId.equals(nullLeafId))) {
				String curr = rightTreeId;
				left = false;
				leftSide = false;
				do {
					RBTree parent = currTree;
					currTree = (RBTree) TMProxy.getTMProxy().read(curr, context.getContextId());
					Logger.debug(context.getContextId()+ " moving to left "+currTree.getVal());
					map.put(curr, parent);
					curr = currTree.getLeft();
					if (!(curr.equals(nullLeafId)))
						left = true;
				} while (!(curr.equals(nullLeafId)));
				Logger.debug(context.getContextId()+ " Deleting from right leaf and currTree is "+currTree.getVal());
			}
			
			// currTree is n
			RBTree parent = getParentWritableCopy(currTree, map, context);

			if (leftSide) {
				NId = currTree.getLeft();
			} else {
				NId = currTree.getRight();
			}
			
//			if (!(NId.equals(nullLeafId)))
			map.put(NId, parent);
				
			bst = (RBTree) TMProxy.getTMProxy().write(bst.getId(), context.getContextId());
			currTree = (RBTree) TMProxy.getTMProxy().write(currTree.getId(), context.getContextId());
			Logger.debug(context.getContextId()+ " old val is "+ bst.getVal() +" new val is "+currTree.getVal());
			bst.setVal(currTree.getVal());
			
			RBTree N = nullLeaf;
			if (!(NId.equals(nullLeafId))) {
				N = (RBTree) TMProxy.getTMProxy().write(NId, context.getContextId());
			}
			
			if (currTree.getId().equals("root") || parent.getId().equals("root"))
				delete_one(N, currTree, map, context, left);

			if (left) {
				parent.setLeft(currTree.getRight());
				Logger.debug(context.getContextId()+ " Setting parent "+parent.getVal() +"'s left child to "+currTree.getLeft());
			} else {
				parent.setRight(currTree.getLeft());
				Logger.debug(context.getContextId()+ " Setting parent "+parent.getVal() +"'s right child to "+currTree.getRight());
			}
		}
	}

	public static void delete_one(RBTree N, RBTree parent, HashMap<String,RBTree> map,
			Context context, boolean leftSide) throws AbortException {

//		/* N is black */
//		if (N == null) {
//			if (parent.getColor().equals(black)) {
//				System.out.println("Need rebalancing");
//				deleteCase1(parent, map, context);
//			} else {
//				System.out.println("No need for rebalancing");
//			}
//		} else {

		if (parent.getColor().equals(black)) {
			if (N.getColor().equals(red)) {
				N.setColor(black);
			} else {
				deleteCase1(N, map, context);
			}
		}
//		}
	}

	public static void deleteCase1(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {

		Logger.debug("Delete Case 1");
		if (!N.getId().equals("root")) {
			deleteCase2(N, map, context);
		}
		
	}	


	public static void deleteCase2(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {

		Logger.debug("Delete Case 2");

		ArrayList<RBTree> list = getRelatives(N, map, context);
		RBTree parent = list.get(0);
		RBTree sibling = list.get(1);
		boolean left = true;
		
		Logger.debug("Value for right is "+parent.getRight());
		if (parent.getRight().equals(N.getId()))
			left = false;

		/* sibling in worst case will nullLeaf */
		if (sibling.getColor().equals(red)) {
			parent.setColor(red);
			sibling.setColor(black);
			if (left)
				leftRotate(parent, sibling, map, context);
			else
				rightRotate(parent, sibling, map, context);
		}
		deleteCase3(N, map, context);
	}	

	public static void deleteCase3(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		Logger.debug("Delete Case 3");

		ArrayList<RBTree> list = getRelatives(N, map, context);
		RBTree parent = list.get(0);
		RBTree sibling = list.get(1);
		RBTree siblingLeft = list.get(2);
		RBTree siblingRight = list.get(3);

		if (parent.getColor().equals(black) &&
				sibling.getColor().equals(black) && 
				siblingLeft != null && siblingLeft.getColor().equals(black) &&
				siblingRight != null && siblingRight.getColor().equals(black)) {
			sibling.setColor(red);
			deleteCase1(parent, map, context);
		} else {
			deleteCase4(N, map, context);
		}

	}

	public static void deleteCase4(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		Logger.debug("Delete Case 4");

		ArrayList<RBTree> list = getRelatives(N, map, context);
		RBTree parent = list.get(0);
		RBTree sibling = list.get(1);
		RBTree siblingLeft = list.get(2);
		RBTree siblingRight = list.get(3);

		if (parent.getColor().equals(red) &&
				sibling.getColor().equals(black) && 
				siblingLeft != null && siblingLeft.getColor().equals(black) &&
				siblingRight != null && siblingRight.getColor().equals(black)) {
			sibling.setColor(red);
			parent.setColor(black);
		} else {
			deleteCase5(N, map, context);
		}
	}

	public static void deleteCase5(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		Logger.debug("Delete Case 5");

		ArrayList<RBTree> list = getRelatives(N, map, context);
		RBTree parent = list.get(0);
		RBTree sibling = list.get(1);
		RBTree siblingLeft = list.get(2);
		RBTree siblingRight = list.get(3);

		if (sibling.getColor().equals(black)) {

			if (N.getId().equals(parent.getLeft()) &&
					siblingRight != null && siblingRight.getColor().equals(black) &&
					siblingLeft != null && siblingLeft.getColor().equals(red)) {
				sibling.setColor(red);
				siblingLeft.setColor(black);
				rightRotate(sibling, siblingLeft, map, context);
			} else if (!N.getId().equals(parent.getLeft()) &&
					siblingLeft != null && siblingLeft.getColor().equals(black) &&
					siblingRight != null && siblingRight.getColor().equals(red)) {
				sibling.setColor(red);
				siblingRight.setColor(black);
				leftRotate(sibling, siblingRight, map, context);
			}
		}

		deleteCase6(N, map, context);
	}

	public static void deleteCase6(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		Logger.debug("Delete Case 6");

		ArrayList<RBTree> list = getRelatives(N, map, context);
		RBTree parent = list.get(0);
		RBTree sibling = list.get(1);
		RBTree siblingLeft = list.get(2);
		RBTree siblingRight = list.get(3);
		
		sibling.setColor(parent.getColor());
		parent.setColor(black);

		if (N.getId().equals(parent.getLeft())) {
			if (siblingRight != null) {
				siblingRight.setColor(black);
				leftRotate(parent, sibling, map, context);
			}
		} else {
			if (siblingLeft != null) {
				siblingLeft.setColor(black);
				rightRotate(parent, sibling, map, context);
			}
		}
	}
	
	public static ArrayList<RBTree> getRelatives(RBTree N, HashMap<String,RBTree> map, Context context) throws AbortException {
		ArrayList<RBTree> list = new ArrayList<RBTree>();

		RBTree parent = getParentWritableCopy(N, map, context);
		RBTree sibling = null;
		boolean left = true;
		RBTree siblingLeft = null;
		RBTree siblingRight = null;


		/* parent will have non-null children, left is for N */
		if (parent.getRight() != null && 
				parent.getRight().equals(N.getId())) {
			left = false;
		}

		if (left) {
			if (parent.getRight() != null)
				sibling = (RBTree) TMProxy.getTMProxy().write(parent.getRight(), context.getContextId());
		} else {
			if (parent.getLeft() != null)
				sibling = (RBTree) TMProxy.getTMProxy().write(parent.getLeft(), context.getContextId());
		}

		if (sibling!= null && sibling.getLeft() != null)
			siblingLeft = (RBTree) TMProxy.getTMProxy().write(sibling.getLeft(), context.getContextId());

		if (sibling!= null && sibling.getRight() != null)
			siblingRight = (RBTree) TMProxy.getTMProxy().write(sibling.getRight(), context.getContextId());

		list.add(parent);
		list.add(sibling);
		list.add(siblingLeft);
		list.add(siblingRight);
		return list;
	}

}



